# @Time    : 2020/6/19 20:13
# @Author  : T-
# @Site    : 
# @File    : 19-Remove Nth Node From End of List.py
# @Software: PyCharm

from utils import ListNode

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # method-1: 两次遍历算法
        # 删除从列表开头数起的第 (L−n+1) 个结点
        # 第一次遍历，找出L
        # 第二次遍历移动哑结点到 (L-n) 位置，把 L-n 指向 L-n+2

        # 哑结点，用来简化极端情况，如只有一个结点，或需要删除列表头部
        dummy = ListNode(-1)
        dummy.next = head
        length = 0
        first = head
        while first:
            length += 1
            first = first.next
        length -= n     # length = L-n
        first = dummy
        while length > 0:
            length -= 1
            first = first.next
        # L-n位置
        first.next = first.next.next
        return dummy.next

        # method-2:一次遍历算法(头插法)
        # 使用双指针方法
        # 第一个指针从开头移动n+1，第二个指针从头出发(两个指针被n个结点分开）
        # 同时移动两个指针保持间隔，直到第一个指针到达最后一个结点，此时第二指针指向要删除的第n个结点
        # 哑结点
        dummy = ListNode(-1)
        dummy.next = head
        # q为前指针，p为后指针
        p = dummy
        q = dummy
        if n == 0:
            return dummy.next
        else:
            # 将q移动n步
            for i in range(n):
                q = q.next
            while q.next:
                p, q = p.next, q.next
            p.next = p.next.next    # p所指位置为第n-1个
            return  dummy.next












